function quickSort (arr: Array<number>): Array<number> {
  function sort(arr: Array<number>, start: number, end: number) {
    if (start >= end) {
      return
    }
    let i = start
    let j = end
    let pivot = arr[start]
    while (i < j) {
      while (i < j && arr[j] > pivot) {
        j--
      }
      if (i < j) {
        arr[i] = arr[j]
        i++
      }
      while ( i < j && arr[i] < pivot) {
        i++
      }
      if (i < j) {
        arr[j] = arr[i]
        j--
      }
    }
    arr[i] = pivot
    sort(arr, start, i - 1)
    sort(arr, i + 1, end)
  }

  sort(arr, 0, arr.length - 1)
  return arr
}

console.log(quickSort([3,3,3,1,3,3,3,3,3]))